package link;

import org.junit.Test;


import java.util.Stack;


//单链表创建和遍历
public class LinkList {

    @Test
    public void test() {
        //创建一个单链表
        SingLinkList singLinkList = new SingLinkList(); //已经加载了头节点
        //创建英雄节点
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
        HeroNode hero5 = new HeroNode(5, "玛丽亚", "***");
        //按添加顺序来添加的子节点
        //        singLinkList.add(hero1);
        //        singLinkList.add(hero2);
        //        singLinkList.add(hero3);
        //        singLinkList.add(hero4);
        //        singLinkList.add(hero5);
        //通过no 排名来添加节点
        singLinkList.addOrderByNo(hero4);
        singLinkList.addOrderByNo(hero2);
        singLinkList.addOrderByNo(hero3);
        singLinkList.addOrderByNo(hero1);
        singLinkList.addOrderByNo(hero5);
        singLinkList.addOrderByNo(hero5);
        singLinkList.show();
        //修改节点
        HeroNode newNode=new HeroNode(5,"超级玛丽亚","******");
        singLinkList.update(newNode);
        System.out.println("修改后的数据:");
        singLinkList.show();
        //删除节点
        singLinkList.delete(3);
        System.out.println("删除后的数据:");
        singLinkList.show();
    }

    @Test
    public  void test2(){
      //创建一个单链表
        SingLinkList slist = new SingLinkList(); //已经加载了头节点
        //创建英雄节点
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
        HeroNode hero5 = new HeroNode(5, "玛丽亚", "***");
        slist.add(hero1);
        slist.add(hero2);
        slist.add(hero3);
        slist.add(hero4);
        slist.add(hero5);
        //求单链表中有效节点的个数
        int size=slist.getLength(slist.getHeadNode());
        System.out.println("单链表中有效节点的个数:"+size);
        HeroNode node = slist.findNode(slist.getHeadNode(), 3);//倒数第三
        System.out.println("单链表倒数第三个:"+node.toString());
        System.out.println("单链表的正序:");
        slist.show();
        System.out.println("下面是单链表的反转:");
        //5.单链表的反转 结构上发生了改变
        HeroNode newNode=slist.reserveNodeList(slist.getHeadNode());
        HeroNode temp=newNode;
        slist.getHeadNode().next=temp.next;
        slist.show();

        System.out.println("从尾到头打印单链表(Stack 栈 先进后出)");
        //从尾到头打印单链表(Stack 栈 先进后出)
        slist.StackNode(slist.getHeadNode());

    }



    }


//定义一个单链表
class SingLinkList {
    //定义一个头节点   方便找到初始位置
    HeroNode headNode = new HeroNode(); //头节点 里面不要任何的数据 单纯的定位


    public HeroNode getHeadNode() {
        return headNode;
    }
    //.合并两个有序的单链表，合并之后的链表仍然有序
    public SingLinkList MergeLinked(HeroNode node1,HeroNode node2){
        SingLinkList newList=new SingLinkList();
        HeroNode newNode=newList.getHeadNode();
        HeroNode temp1=node1;
        HeroNode temp2=node2;
        HeroNode temp3;
        if(temp1.next==null||temp2.next==null){
            System.out.println("链表为空，无需合并");
        }
        HeroNode temp = newNode; //定义一个辅助遍历，因为头节点不能动，类似于指针
        while((temp1=temp1.next)!=null){
            temp.next = temp1;  //头节点 -> node ->....
            temp=temp.next;
        }
        //把链表1 所有的值添加到了新链表
        System.out.println("输出newList:");
        HeroNode t = newNode; //定义一个辅助遍历，因为头节点不能动，类似于指针
        while ((t = t.next) != null) {
            System.out.println(t.toString());
        }
        System.out.println("添加进新链表");
        //再遍历链表2,链表二的值依次按顺序添加到新链表
        while (temp2.next!=null){
            System.out.println(temp2);
            temp3=newList.getHeadNode();//重新使temp3->新链表头节点的下一个
            while (temp3.next!=null){
                // 1  11 21 31 41
                // 10 22 24 38 50
                //如果 temp2.no(10) <1
                if(temp2.next.no<temp3.next.no){
                    //就插到这个temp3的前面
                    temp2.next=temp3.next;
                    temp3.next=temp2;
                }else{
                    //不小于就插temp3.next在后面即可;
                    temp2.next=temp3.next.next;
                    temp3.next.next=temp2;
                }
                temp3=temp3.next;
            }
            temp2=temp2.next;
        }
        return newList;
    }
    //利用栈进行从尾到头打印
    public void StackNode(HeroNode node){
        Stack<HeroNode>stack=new Stack<HeroNode>();
        if (node.next == null) {
            System.out.println("空数据~~~~~");
            return;
        }
        HeroNode temp= node; //定义一个辅助遍历，因为头节点不能动，类似于指针
        while ((temp = temp.next) != null) {
            stack.add(temp);
        }
        System.out.println(stack.toString());
       while(stack.size()>0){
           System.out.println(stack.pop());
       }
    }

    //查找单链表中的倒数第k个节点
    public HeroNode findNode(HeroNode node,int k){
        HeroNode temp=node.next; //指向第一个有效节点
        //统计传过来的链表的有效个数
        int count=getLength(temp);
        if(count<=0){
            return null;
        }else {
        //倒数k个 =count-k
        int all=count-k;
            while(all>=0){
                temp=temp.next;
                all--;
            }
            return temp;
        }
    }

    //5.单链表的反转 结构上发生了改变
    public  HeroNode  reserveNodeList(HeroNode node){
        HeroNode temp=node.next;
        if(temp==null){
            System.out.println("空链表~");
            return null;
        }
        //定义一个新的表头 , 把老链表的所有节点遍历，依次把节点放到新链表的开始位置。
        HeroNode newNode=new HeroNode();
        HeroNode cur=null;
        while (temp!=null){
            cur=temp.next;   //先用cur保存下一个节点  表头->temp->temp.next
            temp.next=newNode.next; //给新表连接 新表头->temp
            newNode.next=temp;
            temp=cur;   //temp->temp.next
        }
        return newNode;
    }


    //求点链表中有效节点的个数
    public  int getLength(HeroNode node){ //传来头节点
        HeroNode temp=node;
        if(temp.next==null){
            return 0;  //没有数据
        }
        int length=0;
        while((temp=temp.next)!=null){
            length++;
        }
        return length;
    }


    //删除节点  1.找到该节点的前一个节点  再temp.next=temp.next.next
    public void delete(int no) {
        HeroNode temp = headNode;
        boolean flag = false;
        while (temp != null) {
            if (temp.next.no == no) {
                flag = true;  //找到该节点
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.next = temp.next.next;
            //没有引用的节点，gc(),垃圾回收机制会回收
        } else {
            System.out.println("链表里没有该节点~");
        }
    }

    //修改节点
    public void update(HeroNode node) {
        HeroNode temp = headNode;
        boolean flag = false;
        while (temp != null) {
            if (temp.next.no == node.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.next.name = node.name;
            temp.next.nickName = node.nickName;
        } else {
            System.out.println("链表里没有该节点~");
        }
    }


    //按照 no 排名 按顺序来添加
    //1.先判断链表里的no 和node.no 是不是重复
    //2.找到 比no大的节点的前面节点。也就是 temp.next.no>node.no
    public void addOrderByNo(HeroNode node) {
        HeroNode temp = headNode;
        boolean flag = false;
        while (temp!=null) {  //当temp==null 结束循环
            if (temp.next == null) {
                temp.next=node;
                break;
            }
            if (temp.next.no == node.no) {
                flag = true;  //找到了重复的id
                break;
            } else if (temp.next.no > node.no) {
                node.next = temp.next;
                temp.next = node;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            System.out.printf("重复%d编号，不能添加!\n", node.no);
        }

    }


    //添加节点 默认添加到最后

    //添加节点

    public void add(HeroNode node) {
        //首先要找到最后一个节点  如果最后一个节点.next==null  那么这个就是最后节点
        HeroNode temp = headNode; //定义一个辅助遍历，因为头节点不能动，类似于指针
        while (true) {
            if (temp.next == null) {  //找到最后节点
                break;
            }
            temp = temp.next; //依次往后遍历
        }
        temp.next = node;  //头节点 -> node ->....
    }

    //遍历所有节点
    public void show() {
        if (headNode.next == null) {
            System.out.println("空数据~~~~~");
            return;
        }
        HeroNode temp = headNode; //定义一个辅助遍历，因为头节点不能动，类似于指针
        while ((temp = temp.next) != null) {
            System.out.println(temp.toString());
        }
    }


}

//定义一个英雄节点
class HeroNode {
    int no;
    String name;
    String nickName; //昵称
    HeroNode next;  //默认是null

    public HeroNode() {
    }

    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + ", nickName='" + nickName + "}'";
    }
}
